/**
 * 
 */
package string;

import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;

import utils.PrintUtils;

/**
 * @author Michael
 * You are given a string, S, and a list of words, L, 
 * that are all of the same length. Find all starting indices 
 * of substring(s) in S that is a concatenation of each word 
 * in L exactly once and without any intervening characters.
 * For example, given:
 * S: "barfoothefoobarman"
 * L: ["foo", "bar"]
 * You should return the indices: [0,9].
 * (order does not matter).
 */
public class SubstringWithConcatenationOfAllWords {

	public static ArrayList<Integer> findSubstring1(String str, String[] list) {
		assert (str!= null && !str.isEmpty());
		assert (list.length > 0);
		
		ArrayList<Integer> result = new ArrayList<Integer>();
		Map<String, Integer> counter = new HashMap<String, Integer>();
		for (String word : list) {
			if (counter.containsKey(word)) {
				counter.put(word, counter.get(word) + 1);
			}
			else {
				counter.put(word, 1);
			}
		}
		
		int wordSize = list[0].length();
		loop: for (int i = 0; i < str.length() - list.length * wordSize; i++) {
			String sub = str.substring(i, i + wordSize);
			if (counter.containsKey(sub)) {
				Map<String, Integer> found = new HashMap<String, Integer>();
				found.put(sub, 1);
				for (int j = i + wordSize; j < i + list.length * wordSize; j = j + wordSize) {
					String postfix = str.substring(j, j + wordSize);
					if (!counter.containsKey(postfix)) {
						continue loop;
					}
					if (!found.containsKey(postfix)) {
						found.put(postfix, 1);
					}
					else {
						found.put(postfix, found.get(postfix) + 1);
					}
					
					if (found.get(postfix) > counter.get(postfix)) {
						continue loop;
					}
				}
				result.add(i);
			}
		}
		
		
		
		return result;
	}
	
	
    public static ArrayList<Integer> findSubstring(String S, String[] L) {  
    	ArrayList<Integer> ans = new ArrayList<Integer>();
    	int m = L[0].length();
    	Map<String, Integer> count = new HashMap<String, Integer>(); 
    	Map<String, Integer> found = new HashMap<String, Integer>();
    	for (String l : L) {
    		if (count.get(l) == null) 
    			count.put(l, 1); 
    		else count.put(l, count.get(l) + 1);
    	}
    	
    	loop: for (int i = 0; i <= S.length() - L.length * m; i++) {
    		String sub = S.substring(i, i + m);
    		if (count.get(sub) != null) {
    			found.clear();
    			found.put(sub, 1);
    			for (int j = 1; j < L.length; j++) {
    				int s = i + j * m;
    				sub = S.substring(s, s + m); 
    				Integer toFind = count.get(sub);
    				if (toFind == null) 
    					continue loop; 
    				Integer foundVal = found.get(sub);        
    				int k = foundVal == null ? 1 : foundVal + 1;    
    				if (k > toFind) 
    					continue loop;               
    				found.put(sub, k);                
    			}               
    			ans.add(i); 
    		}       
    	}         
    	return ans; 
    }
	
	
	/**
	 * 
	 */
	public SubstringWithConcatenationOfAllWords() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
		String[] L = { "fooo", "barr", "wing", "ding", "wing" };
		PrintUtils.printList(findSubstring(S, L));

	}

}
